The present system describes methods for use in the deletion of transient timer entries from their positional locations in a circular queue of fixed timer entries.
In many computer networks, computerized telephone and billing systems, etc., there are intercommunication mechanisms in computers and other types of systems which handle multiple events, where such mechanisms are often presented with the problem of scheduling a certain event to happen at a particular time which is to be arranged for set-up in the system.
Many memory systems for example, have queues of items to be accessed or handled in a particular sequence. Many programs have lists of instructions which are sequenced also to be handled in a particular arrangement of time events. Sometimes, thousands of different items are placed in queues in order to be available for access in a particular sequence or order.
For example, in the compilation of a telephone directory or a directory of certain businesses in a certain location or a directory of the names of people associated with a certain group, these are all examples of data words or information which are placed in queues and which may be accessed, acquired and used or deleted at certain moments of time.
Additionally, once such a list is compiled, it is very often necessary to place insertions into the queue list, for example, new person""s names may be added to a group organization list, or new telephone numbers and addresses and names may be put in a telephone book. Similarly, and often in Kerberos Security Systems, a list of authenticated users and appropriate passwords and tickets may be involved in a list of such useful items.
In each and any of the cases, when it is necessary to add to a particular list, it is sometimes a rather magnitudinous task to achieve this type of event when there is required the normal situation where the system must check through each of the items in the list step-by-step until it reaches its selected position where the insertion must be made, after which a stop operation must occur, and after which the new item is inserted into the system which performs the completion of this operation. However, in so doing, sometimes thousands and thousands of entries must be sequenced through to find the exact point where the new insertion is to be made. This is very time-consuming and exceedingly complex in terms of programming the event to be inserted at a particular point in a large sequence of items in a list.
The normal method for this to happen is that there be a sequential scan of each item, item-by-item, step-by-step, until there is reached or achieved the proper insertion point. The performance cost of queue searching for insertion events which need to be handled at some fixed time in the future, is quite an expensive proposition. However, the queues which must be scanned sequentially are used very often for these purposes because they are simple to implement and maintain, and can reflect the linear nature of the problem to be solved in finding the correct placement point or item into which the new event is to be inserted. Additionally, such a technique is inherently slow, and thus also becomes increasingly costly, as more entries are added to the queue, and considerable time latency factors are involved in the mechanism which of must traverse through the queue in order to find the right new entrance point.
Likewise, the same sort of difficulties arise when an inserted temporary timer entry is now desired to be deleted and removed.
Traditionally, time events are maintained in a queue structure, and each timer event has a value associated with it. The value of the timer event determines when the event would or should happen after the previous timer event has happened.
As an example, if five events are to happen at t+3, then t+8, then t+45, then t+55, then t+56, (where xe2x80x9ctxe2x80x9d is current time), then as an example, the queue may be considered to look as follows:
TE(3) - - - TE(5) - - - TE(37) - - - TE(10) - - - TE(1)
Where xe2x80x9ctxe2x80x9d is the current time and the bracketed value (X) represents the added time, for example, in seconds, which indicates the event as occurring just after the time count that the previous event had occurred.
In this particular operation, after one tick of time has occurred (that is to say, at t+1), then the timer queue could be represented to look as follows:
TE(2) - - - TE(5) - - - TE(37) - - - TE(10) - - - TE(1)
The difference here, is that the first item has now changed from TE(3) to now be TE(2).
With this type of scheme being used, it is seen to be very time-consuming to insert a temporary transient timer event in the queue, since the fixed timer entries need to be scanned from the xe2x80x9cstartxe2x80x9d of the queue until the correct place is found. For example, if a temporary New Timer Event (NTE) is to be added, for example, which is to happen after 48 ticks, then the entries of the timer queue will need to be scanned until an event is found which will happen after 48 ticks, and then the temporary New Timer Event (NTE) needs to be inserted just prior to that event. Thus, in the above example, it would be necessary to scan step-by-step for each of the entries.
Thus, in the above example, the timer queue after the new event insertion (NTE) will now appear as shown below:
TE(2) - - - TE(5) - - - TE(37) - - - TE(4) - - - NTE(6) - - - TE(1)
Thus, the New Timer Event insertion which is TE(6) required the scanning of four previous entries.
Now, in the situation where the queue has thousands of entries, this type of operation will be seen to be very time-consuming in order to provide for a new event insertion. Likewise later when the removal of a temporary New Timer Event (NTE) was desired, the usual and ordinary solution was to sequence through each of the fixed timer entries until the temporary NTE was found so it could then be deleted. Here much wasteful time was consumed.
The present invention involves a method for managing timer events which does not require any scan of the existing entries in the queue, and as a result, provides for an extensive speeding-up for handling the sequence of events which are desired to be utilized in a queue. The new method uses the operation of the timer queue as if it were maintained as a circular queue. Here, the circular queue would have xe2x80x9cNxe2x80x9d permanent entries, where xe2x80x9cNxe2x80x9d is a chosen number, but an arbitrary one depending on the number of permanent entries or FTE (fixed time entries) that one would like to configure into the queue. Also, the number xe2x80x9cNxe2x80x9d then determines the maximum number of timer events that can be handled by this type of configuration.
In the co-pending companion case, U.S. apllication Ser. No. 09/602,692, the major focus was to provide the xe2x80x9cinsertionxe2x80x9d of a transient or temporary timer entry designated as an NTE or new timer entry.
The present disclosure now relates to handling the problem of removing and deleting such a new timer entry (NTE) when it is no longer needed or useful.
The system here contemplates a circular queue of xe2x80x9cNxe2x80x9d fixed timer event (FTE""s) which have been modified with one or more temporary new timer entries (NTEs) and which are now desired to be removed. A specialized program is provided to locate and delete a particular temporary new timer entry (NTE) without the time-consuming problem of linear sequencing through a series of timer events in order to locate and remove a particular new timer event (NTE).
For example, if the timer xe2x80x9ctickxe2x80x9d or xe2x80x9cperiodxe2x80x9d between events is 100 milliseconds, and xe2x80x9cNxe2x80x9d is 9,000, then this queue will then be capable of handling any timer event over a period of 15 minutes. Now, since 100 milliseconds is {fraction (1/10)}th of a second, and 9,000 would equate to 900 seconds, then with 60 seconds to the minute, it is seen that 900 seconds would be equivalent to 15 minutes.
The present method provides for the utilization of a timer queue as a circular queue which has xe2x80x9cNxe2x80x9d permanent entries which are designated as Fixed Timer Entries (FTEs). The chosen number for the configuration, which is the number xe2x80x9cNxe2x80x9d, determines the maximum number of timer events that can be handled.
The method involves allocating xe2x80x9cNxe2x80x9d fixed timer event entries (FTEs) and assigning a timer value of xe2x80x9c1xe2x80x9d to each of these timer events. These timer entries are linked to form a circularly linked list and the addresses of these timer entries are saved in an array which is used to access the fixed elements of the queue directly.
A current Timer Index (current position in a circular Timer Queue) is assigned so that this is equivalent to the current time in ticks, multiplied by the mod list xe2x80x9cNxe2x80x9d.
In general operations, the method permits temporary transient new timer entries (NTEs) to be inserted between two selected fixed timer entries (FTEs). This involves converting the fixed events to xe2x80x9ctimer ticksxe2x80x9d. The program will allocate a new timer event entry, assign a timer value of xe2x80x9c0xe2x80x9d to this entry, then assign a handle to this entry. The new location index will be inserted at xe2x80x9cTimer Indexxe2x80x9d, with the assigned value of (CURRENT_TIME_IN_TICKS+NEW_TIMER_TICKS) mod xe2x80x9cNxe2x80x9d. Then, there is made an insertion of this new timer entry (NTE) prior to the timer entry which is pointed-to by the Timer Index within the Timer Queue.
Likewise, when such an inserted temporary new timer entry (NTE) is ready to be disposed of, the program will locate the assigned handle at the NTE for the purpose of removing and deleting this transient event from the circular queue.